from types import List

"""注意事项
需要注意的是，如果使用的语言对「有符号整数类型」和「无符号整数类型」没有区分，
那么可能会得到错误的答案。这是因为「有符号整数类型」（即 int 类型）
的第 3131 个二进制位（即最高位）是补码意义下的符号位，对应着 -2^{31}，而「无符
号整数类型」由于没有符号，第 3131 个二进制位对应着 2^{31}。因此在某些语言（例如
Python 中需要对最高位进行特殊判断。

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/single-number-ii/solution/zhi-chu-xian-yi-ci-de-shu-zi-ii-by-leetc-23t6/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
"""
# Time Complexity: O(nb) where b=32
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res = 0
        for i in range(32):
            _sum = sum((n >> i) & 1 for n in nums)
            if _sum % 3:
                # python 需要对最高位做特殊判断
                if i == 31:
                    res -= (1 << i)
                else:
                    res |= (1 << i)
        return res
